The present invention relates generally to mechanisms and methods for routing data packets between nodes within a network. More specifically, the present invention relates to methods and apparatus for routing data packets from a data queue through a protocol stack.
FIG. 1 is a diagrammatic representation of a conventional network configuration 100. As shown, data packets 104 are held within a plurality of data queues 102. For example, data packets 104a, 104b, and 104c are held within a first data queue, data packet 104d is held within a second data queue, data packet 104e is held within a third data queue, etc.
As shown, there are various types of data that go to the different data queues 102. For example, internet protocol (IP) data 10 goes to a first data queue and a second data queue; packet assembler disassembler (PAD) data 12 goes to another data queue; qualified logical link control (QLLC) data 14 goes to yet another data queue; and data link switching (DLSW) data 16 goes to yet another data queue.
The network configuration 100 also includes a plurality of diverse protocol stacks through which the data or data packets will be transmitted, and each protocol stack has one or more associated protocol levels (also referred to as protocol layers or contexts). In other words, each data packet is associated with one of the protocol stacks and will eventually be sent through the associated protocol stack. For example, a data packet 104e will be transmitted through an associated protocol stack that includes a virtual circuit (VC) protocol layer 112b, an X.25 protocol layer 110, a link logic control (LLC2) protocol layer 108a, and a physical protocol layer 106 associated with a hardware device (not shown). The hardware device is coupled to other hardware devices (not shown) of other network nodes (not show), such as another router or end destination.
The term protocol is defined as any type of information format that is used to communicate between any independent entities, such as two network nodes.
Each data queue is associated with one or more protocols (herein referred to as a “protocol stack”), and these particular associations depend on the requirements of the particular application being implemented. For example, Internet Protocol data packets are transmitted directly from a data queue to the physical layer 106. As shown, data packet 104g is associated with the physical protocol layer 106 and is sent from the data queue to the physical layer 106. Likewise, data packets 104a through 104c are also only associated with the physical protocol layer 106.
Data packets may travel through various protocols before reaching the physical layer 106. For example, data packet 104f is associated with the virtual circuit (VC) protocol layer 112a, the X.25 protocol layer 110, the LLC2 protocol layer 108a, and the physical protocol layer 106. Likewise data queue 104e is associated with the VC protocol layer 112b, the X.25 protocol layer 110, the LLC2 protocol layer 108a, and the physical protocol layer 106. By way of another example, data packet 104d is only associated with the LLC2 protocol layer 108e and the physical protocol layer 106.
The data queues represent any suitable queuing mechanism for holding data packets at a point above a plurality of protocol layers. For example, the data queues may simply hold the data pending transmission in the order received. In another example, the data queues may control the quality of service provided to data pending transmission by organizing data into a plurality of queues that each assert a claim of dynamic strength on an opportunity to send. The data queues may be associated or located on any suitable type of data transmission device, such as a router device. A router is defined loosely as meaning any network node for receiving and transmitting data packets from and to another network node.
Each of the protocol layers typically communicate with other similar protocol layers (herein referred to as “peer entities”) within other network devices. For example, the X.25 protocol layer 110 may communicate with another network device, which communication is represented by a virtual communication bus 114. Actually, the X.25 protocol layer 100 communicates with another peer X.25 protocol layer through the LLC2 protocol layer 108a, the physical protocol layer 106, the peer physical protocol layer, and peer LLC2 protocol layer. Likewise, the LLC2 protocol layers 108a and 108b each communicate with a peer LLC2 protocol layer, which communications are represented by virtual communication lines 116a and 116b, respectively. Physical layer 106 is configured to communicate with other peer physical layers of other network hardware devices through communication line 118.
A protocol context communicates with a peer context on another network node by using its lower layer protocol context(s). The conversation commonly includes control information, as well as the user data that is carried on behalf of the context's own overlying protocol context(s). The context control information is originated and terminated by the contexts, whereas the user data is sent from and received by the user(s) of the protocol context in the network node.
Both the user data and control data are commonly presented as user data to the underlying protocol context. A protocol context may be required to prohibit user data communication (e.g., it is congested) while remaining capable of exchanging control information. Thus, a protocol context may need to determine whether it's underlying protocol context path is capable of sending control information while maintaining its own context congestion status of being unable to accept user data. Any user data already accepted and queued by a protocol context may be considered control information and may be sent while the context remains unable to accept additional user data.
Peer protocol layers from different network devices or nodes typically pass control information back and forth through its lower protocol context(s) or layers. For example, a first node's LLC2 protocol context may transmit control data to a second node's LLC2 protocol context to indicate that the second node LLC2 protocol context should cease packet transmission. Likewise, the first node's LLC2 protocol context may transmit information that indicates that the second node's LLC2 context may resume transmission. Since flow control information is generally time-sensitive, transmission of such flow control information should not be unduly delayed.
Data packets are typically sent to the next protocol layer of an associated protocol stack as soon as the data queue is ready to send and the next protocol layer is ready to accept the data packets. For example, data packet 104e is sent to VC protocol context 112b. The data packet is then sent to the next protocol layer as soon as the current protocol layer is able to send and/or the next protocol level is ready to accept. If the next protocol level (e.g., the X.25 protocol 110) is unable to accept the data packet, the data packet is held within a queue of the protocol context itself. For example, if the X.25 protocol context 110 is unable to accept data packets, data packets are held within a queue of VC protocol context 112b. In sum, data packets are held within each protocol queue until a next protocol context is able to accept them.
Although conventional data packet transmission approaches work well under certain conditions, these approaches have associated disadvantages. For example, since data packets are typically sent to the next protocol level as soon as the next level is able to accept data packets, so-called “time warp” effects may occur. That is, when a particular protocol context transfers a data packet downstream to a next protocol context, the particular protocol context loses control of the data packet. Thus, if the particular protocol context subsequently receives a request from a peer protocol context of another network device to stop transmission, this request cannot be applied to data packets that are already resident within the next protocol context. In sum, from the requesting network device's perspective, the particular protocol context appears to disregard the request to cease transmission since the data packets that were sent prior to the request may be received by the requesting network device after the request is made.
One solution to this problem of apparently disregarding requests is to limit the number of data packets that may be held within the underlying protocol contexts. However, this solution results in different problems. For example, the transmission hardware may be unnecessarily limited to using less than its full capacity for transmitting data packets.
Additionally, parallel processing at a particular protocol level becomes a problem when a particular protocol queue within the protocol layer reaches capacity because, for example, the next protocol layer is unable to accept packets. It then becomes difficult to efficiently execute parallel processes within the protocol layer with the filled protocol queue. For instance, when a particular protocol layer passes a data portion to a process that runs concurrently with the receipt of data packets by the particular protocol layer, it may be difficult to reinsert the parallel process' results into the data stream when the protocol queues are overloaded.
One example of a parallel process is a compression routine. A portion of a data packet accepted by a particular protocol context is passed to a compression algorithm while other data packets are accepted, processed, and stored within the protocol context's queue or sent to the next protocol context. In other words, the data portion is input into the compression algorithm and processed by the algorithm while other data packets are accepted into the protocol queue. The compression algorithm may not be able to output its results when the protocol queue is at or near capacity. Additionally, if traffic is heavy, the compression algorithm may not be able to output its results for a significantly long period of time.
In view of the foregoing, there is a need for improved data packet transmission mechanisms and techniques for efficiently controlling transmission of data packets from a network device's data queues through one of a diverse set of protocol stacks.